/* 
 * File:   LZ77.cpp
 * Author: Daniela Meneses
 *
 * Created on April 3, 2013, 5:19 PM
 */

#include <cstdio>
#include <string.h>
#include <stdio.h>
#include <string>
#include <stdlib.h>
#include "LZ77.h"

using namespace std;

/**
 * Structure to manage the compression and decompression task.
 */
struct Pointer
{
    /**
     * Steps that the index has to get back to copy elements.
     */
    int backSteps;
    /**
     * Number of elements that 
     */
    int charsToCopy;
    char charAfterMatch;
    bool match;

    Pointer()
    {
        memset(this, 0, sizeof (Pointer));
    }
};

/**
 * Finds a string match and build a pointer that will contain the compression data read it from 
 * the input stream.
 * 
 * @param codingPosition Position where the method will search a match in the input stream.
 * @param inputStream Data to find a match to be compressed.
 * @return 
 */
Pointer match(int codingPosition, char* inputStream)
{
    bool found = false;
    Pointer pointer;
    int windowStart = 0;
    int windowEnd = codingPosition;
    while (windowStart < windowEnd && !found)
    {
        if (inputStream[windowStart] == inputStream[codingPosition])
        {
            found = true;
            pointer.match = true;
            pointer.backSteps = codingPosition - windowStart;
            while (inputStream[windowStart] == inputStream[codingPosition] &&
                    windowStart < windowEnd)
            {
                windowStart++;
                codingPosition++;
                pointer.charsToCopy++;
            }
        }
        windowStart++;
    }
    return pointer;
}

/**
 * Write the pointer data into the buffer.
 * 
 * @param pointer Pointer that contains the data.
 * @param output Buffer that will carry the compressed data.
 */
CompressionErrorCode writeOutput(Pointer pointer, std::string & output)
{
    int res = -1;
    int bufferSize = 3;
    char* buffer = new char[bufferSize];
    bool formatted = false;

    while (!formatted)
    {
        res = snprintf(buffer, bufferSize, "(%d,%d)%c", pointer.backSteps, pointer.charsToCopy, pointer.charAfterMatch);

        if (res > bufferSize || res < 0)
        {
            delete[] buffer;
            bufferSize = res + 1;
            buffer = new char[bufferSize];
        }
        else
        {
            formatted = true;
        }
    }

    if (output.max_size() < (output.length() + strlen(buffer))) return INSUFFICCIENT_MEMORY;

    output.append(buffer);
    delete[] buffer;
    return OK;
}

CompressionErrorCode compressLZ77(const CompressionData& input, CompressionData* output)
{
    CompressionErrorCode res = OK;
    std::string builder;

    for (int codingPosition = 0; codingPosition < input.contentSize; codingPosition++)
    {
        Pointer matcher = match(codingPosition, input.content);
        if (matcher.match)
        {
            codingPosition += matcher.charsToCopy;
            matcher.charAfterMatch = input.content[codingPosition];
            res = writeOutput(matcher, builder);
        }
        else
        {
            matcher.charAfterMatch = input.content[codingPosition];
            res = writeOutput(matcher, builder);
        }

        if (res == INSUFFICCIENT_MEMORY) return res;
    }

    output->contentSize = builder.length();
    output->content = new char[builder.length() + 1];
    builder.copy(output->content, builder.length(), 0);
    output->content[builder.length()] = '\0';

    return res;
}

/**
 * Read the necessary data to build a pointer.
 * 
 * @param inputStream Input to read the pointer data.
 * @param index Where to start to read the data.
 * @return Builded pointer.
 */
Pointer readOutput(char* inputStream, int index)
{
    inputStream += index;
    Pointer pointer;
    sscanf(inputStream, "(%d,%d)%c", &pointer.backSteps, &pointer.charsToCopy, &pointer.charAfterMatch);
    return pointer;
}

CompressionErrorCode decompressLZ77(const CompressionData& input, CompressionData* output)
{
    std::string builder;
    int index = 0;
    while (index < input.contentSize)
    {
        Pointer pointer = readOutput(input.content, index);
        if ((pointer.charsToCopy + builder.length()) > builder.max_size()) return INSUFFICCIENT_MEMORY;
        
        if (pointer.backSteps == 0)
        {
            builder.append(&pointer.charAfterMatch);
        }
        else
        {
            char copiedString[pointer.charsToCopy + 1];
            int copyStartPosition = builder.length() - pointer.backSteps;
            builder.copy(copiedString, pointer.charsToCopy, copyStartPosition);
            copiedString[pointer.charsToCopy] = '\0';
            builder.append(copiedString);
            builder.append(&pointer.charAfterMatch);
        }

        index++;

        while (input.content[index] != '(' && index < input.contentSize)
        {
            index++;
        }
    }

    output->contentSize = builder.length();
    output->content = new char[builder.length() + 1];
    builder.copy(output->content, builder.length(), 0);
    output->content[builder.length()] = '\0';
    return OK;
}
